package leetcode.datastruct1;

import java.util.HashMap;
import java.util.Map;

/**
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
 * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */
public class LeetCode146_LruCache {

    private final Map<Integer, DoubleNode> m = new HashMap<>();
    private final DoubleNodeList dnl = new DoubleNodeList();
    private final int capacity;
    public LeetCode146_LruCache(int capacity) {
        this.capacity = capacity;
    }

    private int get(int k) {
        if (m.containsKey(k)) {
            DoubleNode doubleNode = m.get(k);
            dnl.setTail(doubleNode);
            return doubleNode.v;
        }
        return -1;
    }

    public void put(int k, int v) {
        if (m.containsKey(k)) {
            DoubleNode doubleNode = m.get(k);
            doubleNode.setV(v);
            dnl.setTail(doubleNode);
            return;
        }
        if (m.size() == capacity) {
            DoubleNode removeHead = dnl.removeHead();
            m.remove(removeHead.k);
            m.put(k, dnl.add(k, v));
        }else {
            m.put(k, dnl.add(k, v));
        }
    }

    class DoubleNode {
        // 用于移除m中的k
        int k;
        int v;
        DoubleNode pre;
        DoubleNode next;

        public DoubleNode(int k, int v) {
            this.k = k;
            this.v = v;
        }

        public void setV(int v) {
            this.v = v;
        }
    }

    class DoubleNodeList {
        DoubleNode head;
        DoubleNode tail;

        public DoubleNode add(int k, int v) {
            DoubleNode newNode = new DoubleNode(k, v);
            if (head == null) {
                head = tail = newNode;
            }else {
                tail.next = newNode;
                newNode.pre = tail;
                tail = newNode;
            }
            return newNode;
        }

        public DoubleNode removeHead() {
            DoubleNode rHead = head;
            // 只有一个节点
            if (head == tail) {
                head = tail = null;
            }else {
                head = head.next;
                head.pre.next = null;
                head.pre = null;
            }
            return rHead;
        }
        public void removeNode(DoubleNode removeNode) {
            if (removeNode == head) {
                head = removeNode.next;
                head.pre = null;
                removeNode.next = null;
            }else if (removeNode == tail) {
                tail = removeNode.pre;
                tail.next = null;
                removeNode.pre = null;
            }else {
                removeNode.pre.next = removeNode.next;
                removeNode.next.pre = removeNode.pre;
                removeNode.pre = null;
                removeNode.next = null;
            }
        }
        public void setTail(DoubleNode newTail) {
            if (tail == newTail) {
                return;
            }else if (head == newTail) {
                head = newTail.next;
                newTail.next = null;
                head.pre = null;

                tail.next = newTail;
                newTail.pre = tail;

                tail = newTail;
            }else {
                newTail.pre.next = newTail.next;
                newTail.next.pre = newTail.pre;
                newTail.pre = null;
                newTail.next = null;

                tail.next = newTail;
                newTail.pre = tail;

                tail = newTail;
            }
        }
    }

    public static void main(String[] args) {
        LeetCode146_LruCache leetCode146LruCache = new LeetCode146_LruCache(1);
        leetCode146LruCache.put(2, 1);
        leetCode146LruCache.get(2);
        leetCode146LruCache.put(3, 2);
        leetCode146LruCache.get(2);
        leetCode146LruCache.get(3);

        // System.out.println("leetCode146LruCache.get(1) = " + leetCode146LruCache.get(1));
    }
}
